package org.algorithm.熊猫.数组.二月;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author 熊猫
 * @version 1.0
 * @date 2022/03/06 9:38 PM  周三题目
 * @description: 前缀和
 * <p>
 * security = [5,3,3,3,5,6,2], time = 2
 * <p>
 * 参考题解： https://leetcode-cn.com/problems/find-good-days-to-rob-the-bank/solution/gong-shui-san-xie-qian-zhui-he-yun-yong-gf604/
 * uri： https://leetcode-cn.com/problems/find-good-days-to-rob-the-bank/
 */
public class 适合打劫银行的日子 {

    public static void main(String[] args) {
        int[] nums = {1, 2, 5, 4, 1, 0, 2, 4, 5, 3, 1, 2, 4, 3, 2, 4, 8};
        System.out.println(goodDaysToRobBank(nums, 2));
    }


    public static List<Integer> goodDaysToRobBank(int[] security, int time) {
        List<Integer> result = new ArrayList<>(security.length);
        int length = security.length;
        if (time == 0) {
            int i = length - 1;
            while (time <= i) {
                result.add(time++);
            }
            return result;
        }
        if (security.length <= 2 * time) {
            return result;
        }

        int lastIndex = 0;
        int fastIndex = 2 * time;
        for (int i = time; i < length - time; ) {
            if (lastIndex == i && fastIndex == i) {
                //当前索引下标值符合预期
                result.add(i);
                //索引++进行判断下一位
                if (++i >= length - time) {
                    break;
                }
                //前一个索引符合预期，则只需判断多出一位是否符合预期
                lastIndex = i - time;
                fastIndex = i + time;
                if (security[lastIndex] >= security[lastIndex + 1] && security[fastIndex - 1] <= security[fastIndex]
                        && security[i - 1] >= security[i] && security[i] <= security[i + 1]) {
                    lastIndex = i;
                    fastIndex = i;
                }
            } else if (security[lastIndex] >= security[lastIndex + 1] && security[fastIndex - 1] <= security[fastIndex]) {
                lastIndex++;
                fastIndex--;
            } else {
                i++;
                lastIndex = i - time;
                fastIndex = i + time;
            }

        }
        return result;
    }
}
